package hwTwo3;

// 作业 2.3.5
public class TwoKeyQuickSort {

    public static void quickSortTwoKeys(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        partition(array, 0, array.length - 1);
    }

    private static void partition(int[] array, int low, int high) {
        // 选择分区点（pivot），这里选择 1 作为分界值
        int pivot = 1;
        int i = low - 1; // 指针 i 用来标记小于 pivot 的区域

        for (int j = low; j <= high; j++) {
            if (array[j] < pivot) {
                i++;
                // 交换 array[i] 和 array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 此时，所有小于 pivot 的值都在 pivot 左侧，所有大于等于 pivot 的值都在右侧
    }

    public static void main(String[] args) {
        int[] array = {1, 0, 1, 0, 0, 1, 1, 0, 1};
        quickSortTwoKeys(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}